Simulated annealing is a form of stochastic hill-climbing, which takes its inspiration from crytsal formation during annealing in metals. The basic idea is that from a given point nearby states in the fitness landscape are explored (by making small peturbations to the state). In standard hill-climbing the best next state is chosen, but in simulated annealing the next state is chosen stochastically, with probability based on the negative exponential of the fitness function. A temperature parameter changes this behaviour starting hot, meaning that changes to less good states are more likely (allowing exploration), but getting gradually cooler meaning it behaves more like normal best-first hill-climbing. The effect is that the early stages find the best general area of the fitness landscape whereas the later, cool, stage makes fine adjustments within that area.
Note that due to the anealing analogy which is about energy minimisation, lower values are usually deemed 'good' in simulated annealing, so that it is more like a marble rolling downhill towards the lowest point, but with lots of energy initially so that it doesn't get stuck in local minima.
Defined on pages 76, 76
Used on Chap. 4: pages 76, 77, 81; Chap. 7: page 143; Chap. 9: pages 185, 186; Chap. 18: page 446